// This is the main DLL file.

#include "stdafx.h"

#include "JniCppAlgorithm.h"
#include <stdio.h>
#include<stdlib.h>
#include <windows.h>
#include <fstream>			//for file IO
#include <iostream>			//for cin >> and cout <<
#include <conio.h>			//for _kbhit
#include <string.h>			//for strings
using namespace std;

#define MAX_CONS 25000
#define MAX_COLS 5000
#define MAX_ROWS 5000
#define MAX_FOR_B 25000
#define MAX_FOR_A 35000

unsigned int **contextTemp;	//temporary context matrix for input of cxt file and physical sorting of columns
unsigned int **context;		//the context matrix used for concept mining. 

int mArray;					//size of bit-wise columns in temp context
int nArray;					//size of bit-wise rows in context							

int colOriginal[MAX_COLS];	//maps sorted columns to original order
int colSup[MAX_COLS];		//column support (for sorting and skipping empty columns)
int rowOriginal[MAX_ROWS];	//maps ham-sorted rows to original order

int n;						//no of attributes {0,1,...,n-1} 
int m;						//no of objects    {0,1,...,m-1} 

/************************ tree form of B[MAX_CONS][n] ******************************************/
short int B[MAX_FOR_B];					//intents (tree in linear array)
short int sizeBnode[MAX_CONS];			//the no. of attributes at a node (concept labels)
short int * startB[MAX_CONS];			//pointers to start of intents
int nodeParent[MAX_CONS];				//links to parent node in tree
bool Bparent[MAX_COLS];					//parent intent in Boolean form (attributes currently involved)
short int sizeB[MAX_CONS];				//intent sizes (calculated after con gen for analysis purposes)
short int * bptr = B;					//initialise B pointer to start of B

/************************ linear form of A[MAX_CONS][m] ***************************************/
int A[MAX_FOR_A];						//extents
int * startA[MAX_CONS];					//pointers to start of extents
int sizeA[MAX_CONS];					//extent sizes (calculated after con gen for analysis purposes)

int highc = 1;			//highest concept number
int minIn = 0;			//minimum size of intent (min support)
int minEx = 0;			//minimum size of extent (min support)
int startCol = 0;		//starting column for iteration (to skip empty cols)
int numcons = 0;		//number of concepts
char **anames;			//names of attributes	
char **onames;			//names of objects
const char *cppfname;
//char fname[100];		//context file name


JNIEXPORT void JNICALL Java_jnijavacpp_JniJavaCpp_cppAlgorithm(JNIEnv *env, jobject obj, jstring fname, jint jminIn, jint jminEx)
{

	void InClose(const int c, const int y, const bool *Bparent);	//incremental concept closure functions
	void InCloseMin(const int c, const int y, const bool *Bparent); //same as InClose() but with min support for A.

	void cxtFileInput();			//input context in Burmeister format
	void outputConcepts();			//output concepts using at and ob index numbers
	void outputConceptsNames();		//output concepts using at and ob names
	void outputNoConsBySize();		//"<size> - <number of concepts with intents/extents this size>"
	void sortColumns();				//sort columns in ascending order of support
	void calcAandBsizes();			//calculate sizes of extents and intents
	void outputContext();			//create sub-context and output it as cxt file
	void sortRows();				//sort rows on binary value to reduce Hamming distance

	jboolean isCopy;
	cppfname = env->GetStringUTFChars(fname, &isCopy);
	minIn = (int)jminIn;
	minEx = (int)jminEx;

	cxtFileInput(); //input context file

	cout << "\nSorting...";

	//set initial intent parent to 'no attributes involved'
	for (int i = 0; i < MAX_COLS; i++) Bparent[i] = false;

	/* Initialse concept 0: the supremum */
	/* A[0] = {0,1,...,m-1} - supremum involves all objects */
	for (int i = 0; i < m; i++) A[i] = i;
	startA[0] = &A[0];
	startA[1] = &A[m];
	/* B[0] = {} - supremum initially has no attributes */
	sizeB[0] = 0;
	startB[0] = &B[0];
	nodeParent[0] = -1; //supremun does not have a parent

	for (int i = 0; i < n; i++) colOriginal[i] = i; //init column index array for sorting
	sortColumns();

	/* skip empty columns: note iteration is from right to left (i.e. towards zero) */
	startCol = n - 1;
	while (colSup[startCol] == 0) startCol--;

	sortRows();

	cout << "\nMining concepts...";

	/* mine concepts */
	if (minEx) //if min support for extent is required call InCloseMin()
		InCloseMin(0, startCol, Bparent);
	else
		InClose(0, startCol, Bparent);

	calcAandBsizes();

	outputNoConsBySize();//and count concepts

	cout << "\nNumber of concepts: " << numcons;

	//char reply;
   // cout << "\n\nOutput concepts to file? (y/n): ";
	//cin >> reply;
	//if (reply == 'y'){
	//	cout << "\nOutput names? (y/n): ";
	//	cin >> reply;
	//	if (reply == 'y')
			outputConceptsNames();
	//	else
	//		outputConcepts();
//	cout << "Done.";
//	}
	//if minimum support has been specified, output the reduced context file
	if (minIn>0 || minEx > 0)
		outputContext();

	//cout << "\n\nHit <enter> to finish";
	//while (!_kbhit());
	delete[] context;
	delete onames;
	delete anames;
}

	//********** END MAIN *********************************************************

void InClose(const int c, const int y, const bool *Bparent)
/* c: concept number, y: attribute number, Bparent: parent intent in Boolean form */
{
	bool IsCannonical(const int y, const int * endAhighc, const bool Bchild[]);
	/* y: attribute number, endAhighc: pointer to end of the next extent to be created */
	/* Bchild: the current intent in Boolean form (to skip columns when checking cannonocity of any 'new' extent) */

	int Bchildren[MAX_COLS];							//the attributes that will spawn new concepts
	int numchildren = 0;								//the number of new concepts spawned from current one
	int Cnums[MAX_COLS];								//the concept no.s of the spawned concepts
	bool Bchild[MAX_COLS];								//the current intent in Boolean form

	for (int q = startCol; q >= 0; q--) {
		Bchild[q] = Bparent[q];							//set the child attributes to the parent ones (inheritance)
	}


	if (c){		//if not concept 0, add the spawning attribute to intent
		Bchild[y + 1] = 1;
		*bptr = y + 1;
		bptr++;
		sizeBnode[c]++;
	}
	/*********************** MAIN LOOP *********************************************************
	interate across attribute columns forming column intersetcions with current extent
	********************************************************************************************/
	for (int j = y; j >= 0; --j)	{
		if (!Bchild[j]){									//if attribute is not an inherited one
			int * Ac = startA[c];						//pointer to start of current extent
			int * aptr = startA[highc];					//pointer to start of next extent to be created
			int sizeAc = startA[c + 1] - startA[c];			//calculate the size of current extent
			/* iterate across objects in current extent to find them in current attribute column */
			for (int i = sizeAc; i > 0; i--){
				if (context[*Ac][j >> 5] & (1 << (j % 32))){//context[*Ac][J] where J is byte J div 8, bit J mod 8
					*aptr = *Ac;						//add object to new extent (intersection)
					aptr++;
				}
				Ac++;									//next object
			}
			int size = aptr - startA[highc];			//calculate size of intersection
			if (size){									//if intersection (extent) is not empty
				if (size == sizeAc){						//if extent is unchanged
					*bptr = j;							//add current attribute to intent
					bptr++;
					Bchild[j] = 1;						//record that the attribute will be inherited by any child concepts
					sizeBnode[c]++;						//increment the number of attributes at this node in the B tree
				}
				/* if the intersection is smaller test for cannonicity */
				else if (IsCannonical(j + 1, aptr, Bchild)){	//if the intersection is a new extent, note the child for later spawning:
					Bchildren[numchildren] = j;			//note where (attribute column) it was found,
					Cnums[numchildren++] = highc;		//note the concept number,
					nodeParent[highc] = c;				//note the parent concept number and
					startA[++highc] = aptr;				//note the start of the new extent in A.
				}
			}
		}
	}
	/* spawn child concepts from this parent */
	for (int i = numchildren - 1; i >= 0; i--){
		startB[Cnums[i]] = bptr;						//set the start of the intent in B tree
		InClose(Cnums[i], Bchildren[i] - 1, Bchild);		//close the child concept (next closure starts at j-1 to
	}													//avoid having to create this intersection again)
}

bool IsCannonical(const int y, const int * endAhighc, const bool Bchild[])
		/* y: attribute number, endAhighc: pointer to end of the next extent to be created */
		/* Bchild: the current intent in Boolean form (to skip columns when checking cannonocity of any 'new' concept) */
{
	for (int q = y; q <= startCol; q++)												//iterate back through conext matrix
			if ((!Bchild[q]) && (context[*(startA[highc])][q >> 5] & (1 << (q % 32)))){		//if att not currently involved and there is a X in the 
				int i;																	//first cell checked in the column (1st ob in the intersection)
				int * Ahighc = startA[highc] + 1;											//point to the next cell
				for (i = endAhighc - Ahighc; i > 0; i--){								//and iterate down the column to check for a match
					if (!(context[*Ahighc][q >> 5] & (1 << (q % 32))))break;				//if an empty cell is found, move on to check next column
					Ahighc++;															//otherwise check next cell down
				}
				if (i == 0) return(false);												//if intersection is found, it is not cannonical
			}
		return(true);																	//if intersection is not found, it is cannonical
	}

	/* InCloseMin() is identical to InClose() apart from test for min support instead of test for not-empty intersection */
	/* which gives a small performance benefit */
void InCloseMin(const int c, const int y, const bool *Bparent)
/* c: concept number, y: attribute number, Bparent: parent intent in Boolean form */
{
	bool IsCannonical(const int y, const int * endAhighc, const bool Bchild[]);
	/* y: attribute number, endAhighc: pointer to end of the next extent to be created */
	/* Bchild: the current intent in Boolean form (to skip columns when checking cannonocity of any 'new' extent) */

	int Bchildren[MAX_COLS];							//the attributes that will spawn new concepts
	int numchildren = 0;								//the number of new concepts spawned from current one
	int Cnums[MAX_COLS];								//the concept no.s of the spawned concepts
	bool Bchild[MAX_COLS];								//the current intent in Boolean form

	for (int q = startCol; q >= 0; q--)
		Bchild[q] = Bparent[q];							//set the child attributes to the parent ones (inheritance)

	if (c){												//if not concept 0, add the last attribute to intent
		Bchild[y + 1] = 1;
		*bptr = y + 1;
		bptr++;
		sizeBnode[c]++;
	}
	/*********************** MAIN LOOP *********************************************************
	interate across attribute columns forming column intersetcions with current extent
	********************************************************************************************/
	for (int j = y; j >= 0; --j)	{
		if (!Bchild[j]){									//if attribute is not an inherited one
			int * Ac = startA[c];						//pointer to start of current extent
			int * aptr = startA[highc];					//pointer to start of next extent to be created
			int sizeAc = startA[c + 1] - startA[c];			//calculate the size of current extent
			/* iterate across objects in current extent to find them in current attribute column */
			for (int i = sizeAc; i > 0; i--){
				if (context[*Ac][j >> 5] & (1 << (j % 32))){//context[*Ac][J] where J is byte J div 8, bit J mod 8
					*aptr = *Ac;						//add object to new extent (intersection)
					aptr++;
				}
				Ac++;									//next object
			}
			int size = aptr - startA[highc];			//calculate size of intersection
			if (size >= minEx){	//if intersection is >= min support for extents
				if (size == sizeAc){						//if extent is unchanged
					*bptr = j;							//add current attribute to intent
					bptr++;
					Bchild[j] = 1;						//record that the attribute will be inherited by any child concepts
					sizeBnode[c]++;						//increment the number of attributes at this node in the B tree
				}
				/* if the intersection is smaller test for cannonicity */
				else if (IsCannonical(j + 1, aptr, Bchild)){	//if the intersection is a new extent, note the child for later spawning:
					Bchildren[numchildren] = j;			//note where (attribute column) it was found,
					Cnums[numchildren++] = highc;		//note the concept number,
					nodeParent[highc] = c;				//note the parent concept number and
					startA[++highc] = aptr;				//note the start of the new extent in A.
				}
			}
		}
	}
	/* spawn child concepts from this parent */
	for (int i = numchildren - 1; i >= 0; i--){
		startB[Cnums[i]] = bptr;						//set the start of the intent in B tree
		InCloseMin(Cnums[i], Bchildren[i] - 1, Bchild);	//close the child concept (next closure starts at j-1 to
	}													//avoid having to create this intersection again)
}

void outputConcepts() //output concepts to file
{
	string strData;
	char ibuffer[40];
	//cout << "\n\nOutputting concepts to file...";
	FILE *fp1;
	fp1 = fopen("concepts.txt", "w");


	/* for each concept */
	for (int c = 0; c < highc; c++)
	{
		if (sizeB[c] >= minIn && sizeA[c] >= minEx)
		{
			/* traverse B tree to obtain intent */
			int i = c;									//set i to concept
			while (i >= 0){								//when i==-1, head node is reached
				short int *bptr = startB[i];			//point to start of attributes in first node of this intent
				for (int j = 0; j < sizeBnode[i]; j++){	//iterate attributes at this node
					_itoa_s(colOriginal[*bptr], ibuffer, 10);//convert attribute no. to ASCII
					strData += ibuffer;
					strData += ",";
					bptr++;
				}
				i = nodeParent[i];						//point to next node
			}
			strData += "\t";								//<tab> between intent and extent
			/* obtain extent from A */
			int * aptr = startA[c];						//point to start of extent
			for (int j = 0; j < sizeA[c]; j++){			//iterate objects
				_itoa_s(rowOriginal[*aptr], ibuffer, 10);	//convert object no. to ASCII
				strData += ibuffer;
				strData += ",";
				aptr++;
			}
			strData += "\n";
		}
		fputs(strData.c_str(), fp1);
		strData = "";
	}
	fclose(fp1);
}

void outputConceptsNames() //output concepts to file using object and attribute names
{
	cout << "\n\nOutputting concepts to file...";
	string strData;
	FILE *fp1;

	fp1 = fopen("concepts.txt", "w");

	/* for each concept */
	for (int c = 0; c < highc; c++){
		if (sizeB[c] >= minIn && sizeA[c] >= minEx){
			/* traverse B tree to obtain intent */
			int i = c;									//set i to concept
			while (i >= 0){								//when i==-1, head node is reached
				short int * bptr = startB[i];			//point to start of attributes in first node of this intent
				for (int j = 0; j < sizeBnode[i]; j++){	//iterate attributes at this node
					strData += anames[colOriginal[*bptr]];
					strData += ",";
					bptr++;
				}
				i = nodeParent[i];						//point to next node
			}
			strData += "\t";								//<tab> between intent and extent

			int * aptr = startA[c];						//point to start of extent
			for (int j = 0; j < sizeA[c]; j++){			//iterate objects
				strData += onames[rowOriginal[*aptr]];
				strData += ",";
				aptr++;
			}
			strData += "\n";
		}
		fputs(strData.c_str(), fp1);
		strData = "";
	}
	fclose(fp1);
}

void cxtFileInput()		//input data from Burmeister cxt file
{
	int i, j;			//object and attribute counters
	ifstream cxtFile;
//	cxtFile.open("C:/Users/abdelhaqa/Desktop/JniCpp/JniJavaString/vboutput.cxt");
	cxtFile.open(cppfname);

	cout << "\n\nReading data...";
	char Bchar;
	cxtFile >> Bchar;	//strip out the 'B' at top of Burmeister cxt file!
	cxtFile >> m;		//input number of objects
	cxtFile >> n;		//input number of attributes

	/* create temporary context for sorting*/
	mArray = (m - 1) / 32 + 1;							//calculate size of second dimension (objects) - 1bit per object
	contextTemp = new unsigned int*[n];				//create one dimension of the temporary context
	for (j = 0; j < n; j++){							//for each attribute
		contextTemp[j] = new unsigned int[mArray];	//create a row of objects
		for (i = 0; i<mArray; i++) contextTemp[j][i] = 0;
	}

	/* create context */
	nArray = (n - 1) / 32 + 1;						//calculate size of second dimension (attributes) - 1bit per object
	context = new unsigned int*[m];				//create one dimension of the context
	for (i = 0; i < m; i++){						//for each object
		context[i] = new unsigned int[nArray];	//create a row of attributes
		for (j = 0; j<nArray; j++) context[i][j] = 0;
	}

	/* strip out blank lines in cxt file */
	char blank[256];
	cxtFile.getline(blank, 256);
	cxtFile.getline(blank, 256);

	/* create arrays for object and attribute names */
	onames = new char*[m];
	for (i = 0; i < m; i++) onames[i] = new char[256];
	anames = new char*[n];
	for (i = 0; i < n; i++) anames[i] = new char[256];

	/* get object and attribute names */
	for (i = 0; i < m; i++)
		cxtFile.getline(onames[i], 256);
	for (j = 0; j < n; j++)
		cxtFile.getline(anames[j], 256);

	/* create input row (instance) of context grid to be input from file */
	char *instance;
	int instanceSize = (n + 2);
	instance = new char[instanceSize];
	//ZeroMemory(instance,sizeof(char)*instanceSize);

	/* input instances and translate into temporary context */
	for (i = 0; i < m; i++){								//for each row (object),
		cxtFile.getline(instance, instanceSize);		//get instance.
		for (j = 0; j < n; j++){							//for each attribute,
			if (instance[j] == 'X'){						//if object has the attibute,
				contextTemp[j][(i >> 5)] |= (1 << (i % 32));	//set context bit to true where I is byte: i div 8, bit: i mod 8
				colSup[j]++;							//increment column support for attribute j
			}
		}
	}
	cxtFile.close();
}

void calcAandBsizes()	//calculate sizes of extents and intents of each concept
{
	int highsizeB = 0;							//largest intent generated
	for (int c = 0; c < highc; c++){				//for each concept
		sizeA[c] = startA[c + 1] - startA[c];		//calculate size of extent
		/* calculate size of intent by traversing B tree */
		int i = c;
		while (i >= 0){
			sizeB[c] = sizeB[c] + sizeBnode[i];	//add number of attributes at node i to size
			i = nodeParent[i];					//get the next node (parent)
		}
		if (sizeB[c] > highsizeB) highsizeB = sizeB[c];
	}
	/* add empty infimum if necessary */
	if (highsizeB < n){
		sizeBnode[highc] = n;
		nodeParent[highc] = -1;
		startB[highc] = bptr;
		for (int j = 0; j < n; j++){
			*bptr = j;
			bptr++;
		}
		sizeA[highc] = 0;
		sizeB[highc] = n;
		highc++;
	}
}

void outputNoConsBySize()
{
	/* create arrays to store the number of concepts of each size */
	int *noOfBSize = new int[n + 1];
	ZeroMemory(noOfBSize, sizeof(int)*(n + 1));
	int *noOfASize = new int[m + 1];//[MAX_ROWS];
	ZeroMemory(noOfASize, sizeof(int)*(m + 1));

	/* calculate number of concepts of each size satisfying min supports */
	for (int c = 0; c < highc; c++){
		if (sizeB[c] >= minIn && sizeA[c] >= minEx){
			noOfBSize[sizeB[c]]++;
			noOfASize[sizeA[c]]++;
			numcons++;
		}
	}
	if (noOfBSize[n] == 0 && minIn == 0){
		noOfBSize[n] = 1;
		numcons++;
	}

	/* output list of <size B> - <#concepts> */
	ofstream outBlist;
	outBlist.open("noConsByBsize.txt", 'w');
	outBlist << "<size B> - <#concepts> min A: " << minEx << " min B: " << minIn << "\n";
	for (int c = minIn; c <= n; c++){
		if (noOfBSize[c] > 0) outBlist << c << " - " << noOfBSize[c] << "\n";
	}
	outBlist.close();

	/* output list of <size A> - <#concepts> */
	ofstream outAlist;
	outAlist.open("noConsByAsize.txt", 'w');
	outAlist << "<size A> - <#concepts> min A: " << minEx << " min B: " << minIn << "\n";
	for (int i = minEx; i <= m; i++){
		if (noOfASize[i] > 0) outAlist << i << " - " << noOfASize[i] << "\n";
	}
	outAlist.close();
}

void sortColumns()
{
	int temp, i, j;
	/* bubble sort column indexes (logical sort) - decending order of support*/
	for (i = 0; i < n; i++){
		for (j = 0; j < n - i - 1; j++){
			if (colSup[j] < colSup[j + 1]){
				temp = colSup[j];
				colSup[j] = colSup[j + 1];
				colSup[j + 1] = temp;
				temp = colOriginal[j];
				colOriginal[j] = colOriginal[j + 1];	//keep track of original columns
				colOriginal[j + 1] = temp;
			}
		}
	}

	/* rewrite sorted context (physical sort) */
	int tempColNums[MAX_COLS];
	int rank[MAX_COLS];
	for (j = 0; j < n; j++){
		tempColNums[j] = colOriginal[j]; //use original col nos to index the sort
		rank[colOriginal[j]] = j;			//record the ranking of the column
	}
	for (j = 0; j < n - 1; j++){
		for (i = 0; i < mArray; i++){
			unsigned int temp = contextTemp[j][i];
			contextTemp[j][i] = contextTemp[tempColNums[j]][i];
			contextTemp[tempColNums[j]][i] = temp;
		}
		tempColNums[rank[j]] = tempColNums[j];		//make note of where swapped-out col has moved to using its rank
		rank[tempColNums[j]] = rank[j];
	}

	/* write translated context */
	for (i = 0; i<m; i++){
		for (j = 0; j<n; j++){
			if (contextTemp[j][(i >> 5)] & (1 << (i % 32)))
				context[i][(j >> 5)] |= (1 << (j % 32));
		}
	}
	delete[] contextTemp;
}

void sortRows()
{
	void quickHamsort(int left, int right, int original[]);

	//initialise row pointers and original row indexes
	for (int i = 0; i<m; i++)
		rowOriginal[i] = i;

	quickHamsort(0, m - 1, rowOriginal);

	/* rewrite sorted context (physical sort) */
	int* tempRowNums = new int[MAX_ROWS];
	int* rank = new int[MAX_ROWS];
	for (int i = 0; i < m; i++){
		tempRowNums[i] = rowOriginal[i];	//use original row nos to index the sort
		rank[rowOriginal[i]] = i;			//record the ranking of the row
	}
	for (int i = 0; i < m - 1; i++){
		for (int j = 0; j < nArray; j++){
			unsigned int temp = context[i][j];
			context[i][j] = context[tempRowNums[i]][j];
			context[tempRowNums[i]][j] = temp;
		}
		tempRowNums[rank[i]] = tempRowNums[i];		//make note of where swapped-out row has moved to using its rank	
		rank[tempRowNums[i]] = rank[i];
	}
	delete tempRowNums, rank;
}

void quickHamsort(int left, int right, int original[])
{
	int partitionHam(int left, int right, int pivotIndex, int original[]);

	if (right > left){
		int pivotIndex = left + (right - left) / 2;
		int pivotNewIndex = partitionHam(left, right, pivotIndex, original);
		quickHamsort(left, pivotNewIndex - 1, original);
		quickHamsort(pivotNewIndex + 1, right, original);
	}
}

int partitionHam(int left, int right, int pivotIndex, int original[])
{
	bool biggerHam(int, int);

	int pivotValue = original[pivotIndex];
	original[pivotIndex] = original[right];
	original[right] = pivotValue;//move pivot index to end
	int storeIndex = left;
	for (int i = left; i<right; i++){
		if (biggerHam(original[i], pivotValue)){
			int temp = original[i];
			original[i] = original[storeIndex];
			original[storeIndex] = temp;
			storeIndex++;
		}
	}
	int temp = original[storeIndex];
	original[storeIndex] = original[right];
	original[right] = temp;
	return(storeIndex);
}

bool biggerHam(int i1, int i2)
{
	for (int j = 0; j<nArray; j++){
		if (context[i1][j]>context[i2][j])return true;
		if (context[i2][j]>context[i1][j])return false;
	}
	return false;
}


void outputContext()
{
	cout << "\n\nOutputting context file...";

	/* flags to use to control susequent file output: only output rows and columns that are not empty */
	bool colHasSupport[MAX_COLS];
	bool* rowHasSupport = new bool[MAX_ROWS];
	for (int i = 0; i<m; i++) rowHasSupport[i] = false;
	for (int j = 0; j<n; j++) colHasSupport[j] = false;

	/* zeroise context */
	for (int i = 0; i < m; i++)
		for (int j = 0; j < nArray; j++)
			context[i][j] = 0;

	/* for each concept */
	for (int c = 0; c < highc; c++){
		if (sizeB[c] >= minIn && sizeA[c] >= minEx){				//if concept satisfies min support (is large enough)
			/* traverse B tree to obtain attributes */			//then write it to the new context
			int k = c;											//set i to concept
			while (k >= 0){										//when i==-1, head node is reached
				short int *bptr = startB[k];					//point to start of attributes in first node of this intent
				for (int j = 0; j < sizeBnode[k]; j++){			//iterate attributes at this node
					int b = *bptr;								//obtain original attribute index
					colHasSupport[b] = true;
					bptr++;
					/* obtain extent from A */
					int * aptr = startA[c];						//point to start of extent
					for (int i = 0; i < sizeA[c]; i++){			//iterate objects
						context[*aptr][b >> 5] |= (1 << (b % 32));	//set context cell to false for this (ob,at) pair
						rowHasSupport[*aptr] = true;
						aptr++;
					}
				}
				k = nodeParent[k];								//point to next node
			}
		}
	}

	/*count new number of objects and attibutes in reduced context*/
	int newm = 0;
	int newn = 0;
	for (int i = 0; i<m; i++) if (rowHasSupport[i]) newm++;
	for (int j = 0; j<n; j++) if (colHasSupport[j]) newn++;

	/* output reduced-context Burmeister file */
	FILE *fpsc;
	fpsc = fopen("context.cxt", "w");

	/* output header: B numobs numats */
	fputs("B\n\n", fpsc);
	char nobs[10], nats[10];
	_itoa_s(newm, nobs, 10);
	_itoa_s(newn, nats, 10);
	fputs(nobs, fpsc);
	fputs("\n", fpsc);
	fputs(nats, fpsc);
	fputs("\n\n", fpsc);

	/* output names of objects and attributes */
	for (int i = 0; i < m; i++){
		if (rowHasSupport[i]){
			fputs(onames[rowOriginal[i]], fpsc);
			fputs("\n", fpsc);
		}
	}
	for (int j = 0; j < n; j++){
		if (colHasSupport[j]){
			fputs(anames[colOriginal[j]], fpsc);
			fputs("\n", fpsc);
		}
	}

	/* output reduced context grid - only output non-empty rows/cols	*/
	/* note that the (new) context will be column-sorted in dec order	*/
	char *instance;
	int instanceSize = (newn + 2);
	instance = new char[instanceSize];
	ZeroMemory(instance, sizeof(char)*instanceSize);
	for (int i = 0; i < m; i++){
		int numchars = 0;
		if (rowHasSupport[i]){
			for (int j = 0; j < n; j++){
				if (colHasSupport[j]){
					if (context[i][j >> 5] & (1 << (j % 32)))
						instance[numchars++] = 'X';
					else
						instance[numchars++] = '.';
				}
			}
			instance[newn] = '\n';
			fputs(instance, fpsc);
		}
	}
	fclose(fpsc);
}
